#include "binarytreeheap.h"

//adjust memory capacity 
void AdjustCapacity(PBTHeap pheap)
{
	assert(pheap);
	int newcapa = ONCE_SPACE;
	if (!((pheap->pdata == NULL) || (pheap->capacity == 0)))
	{
		newcapa = pheap->capacity * 2;
	}
	BTHeapData* newpdata = (BTHeapData*)realloc(pheap->pdata, newcapa * sizeof(BTHeapData));
	if (!newpdata)
	{
		perror("AdjustSpace::malloc::");
		return;
	}
	pheap->pdata = newpdata;
	pheap->capacity = newcapa;
}

//swap binary tree heap data
void Swap(BTHeapData* p1, BTHeapData* p2)
{
	assert(p1 && p2);
	//swap p1 pointer data and p2 pointer data
	int temp = *p1;
	*p1 = *p2;
	*p2 = temp;
}

//MAX heap top //adjust up binary tree heap data
void MaxAdjustUp(BTHeapData* pdata, int index)
{
	assert(pdata);
	int indexchild = index;
	int indexfather = (index - 1) / 2;

	//swap binary tree heap child index and father index
	while ((pdata[indexchild] > pdata[indexfather]) && indexchild > 0)
	{
		Swap((pdata + indexchild), (pdata + indexfather));
		indexchild = indexfather;
		indexfather = (indexchild - 1) / 2;
	}
}

//MAX heap top //adjust down binary tree heap data
void MaxAdjustDown(BTHeapData* pdata, int index, int size)
{
	assert(pdata);
	//count father and child index
	int indexfather = index;
	int ichildleft = indexfather * 2 + 1;
	int ichildright = ichildleft + 1;

	//swap binary tree heap child index and father index

	//(left index < size) -> member not empty  
	while (ichildleft < size)
	{
		//if (right index < size) -> (left value or right value) compare (father value)
		if ((ichildright < size) && ((pdata[indexfather] < pdata[ichildleft]) || (pdata[indexfather] < pdata[ichildright])))
		{
			if ((pdata[ichildright] <= pdata[ichildleft]))// && (pdata[indexfather] < pdata[ichildleft]))
			{
				Swap((pdata + indexfather), (pdata + ichildleft));
				indexfather = ichildleft;
				ichildleft = indexfather * 2 + 1;
				ichildright = ichildleft + 1;
			}
			else if ((pdata[ichildleft] < pdata[ichildright]))// && (pdata[indexfather] < pdata[ichildright]))
			{
				Swap((pdata + indexfather), (pdata + ichildright));
				indexfather = ichildright;
				ichildleft = indexfather * 2 + 1;
				ichildright = ichildleft + 1;
			}
		}
		//else if (left index < size) -> (left value) compare (false value)
		else if ((ichildleft < size) && (pdata[indexfather] < pdata[ichildleft]))
		{
			Swap((pdata + indexfather), (pdata + ichildleft));
			indexfather = ichildleft;
			ichildleft = indexfather * 2 + 1;
			ichildright = ichildleft + 1;
		}
		//else end
		else
		{
			return;
		}
	}
}

// MIN heap top //adjust up binary tree heap data
void MinAdjustUp(BTHeapData* pdata, int index)
{
	assert(pdata);
	int indexchild = index;
	int indexfather = (index - 1) / 2;

	//swap binary tree heap child index and father index
	while ((pdata[indexchild] < pdata[indexfather]) && indexchild > 0)
	{
		Swap((pdata + indexchild), (pdata + indexfather));
		indexchild = indexfather;
		indexfather = (indexchild - 1) / 2;
	}
}

// MIN heap top //adjust down binary tree heap data
void MinAdjustDown(BTHeapData* pdata, int index, int size)
{
	assert(pdata);
	//count father and child index
	int indexfather = index;
	int ichildleft = indexfather * 2 + 1;
	int ichildright = ichildleft + 1;

	//swap binary tree heap child index and father index

	//(left index < size) -> member not empty  
	while (ichildleft < size)
	{
		//if (right index < size) -> (left value or right value) compare (father value)
		if ((ichildright < size) && ((pdata[indexfather] > pdata[ichildleft]) || (pdata[indexfather] > pdata[ichildright])))
		{
			if ((pdata[ichildright] >= pdata[ichildleft]))// && (pdata[indexfather] > pdata[ichildleft]))
			{
				Swap((pdata + indexfather), (pdata + ichildleft));
				indexfather = ichildleft;
				ichildleft = indexfather * 2 + 1;
				ichildright = ichildleft + 1;
			}
			else if ((pdata[ichildleft] > pdata[ichildright]))// && (pdata[indexfather] > pdata[ichildright]))
			{
				Swap((pdata + indexfather), (pdata + ichildright));
				indexfather = ichildright;
				ichildleft = indexfather * 2 + 1;
				ichildright = ichildleft + 1;
			}
		}
		//else if (left index < size) -> (left value) compare (false value)
		else if ((ichildleft < size) && (pdata[indexfather] > pdata[ichildleft]))
		{
			Swap((pdata + indexfather), (pdata + ichildleft));
			indexfather = ichildleft;
			ichildleft = indexfather * 2 + 1;
			ichildright = ichildleft + 1;
		}
		//else end
		else
		{
			return;
		}
	}
}

//binary tree heap init
void HeapInit(PBTHeap pheap)
{
	assert(pheap);
	pheap->capacity = 0;
	pheap->pdata = NULL;
	pheap->size = 0;
	AdjustCapacity(pheap);
}

//binary tree heap destroy
void HeapDestroy(PBTHeap pheap)
{
	assert(pheap);
	free(pheap->pdata);
	pheap->capacity = 0;
	pheap->size = 0;
}

//binary tree heap push data
void HeapPush(PBTHeap pheap, BTHeapData value)
{
	assert(pheap);
	//judgment binary tree heap size equal to capacity
	if (pheap->size == pheap->capacity)
		AdjustCapacity(pheap);
	//binary tree heap tail add member
	pheap->pdata[pheap->size] = value;
	printf("heap push value->%d\n", value);
	pheap->size++;
	////MAX heap top //adjust up new member
	//MaxAdjustUp(pheap->pdata, (pheap->size - 1));

	//MIN heap top //adjust up new member
	MinAdjustUp(pheap->pdata, (pheap->size - 1));
}

//binary tree heap pop data
void HeapPop(PBTHeap pheap)
{
	assert(pheap);
	//swap heap head and heap tail
	Swap(pheap->pdata, (pheap->pdata + (pheap->size - 1)));
	//binary tree heap tail add member
	printf("heap pop value->%d\n", pheap->pdata[pheap->size - 1]);
	pheap->size--;
	////MAX heap top //adjust up new member
	//MaxAdjustDown(pheap->pdata, 0, pheap->size);

	//MAX heap top //adjust up new member
	MinAdjustDown(pheap->pdata, 0, pheap->size);
}

//return binary tree heap top data
BTHeapData HeapTop(PBTHeap pheap)
{
	assert(pheap);
	if (pheap->size > 0 && pheap->pdata != NULL)
	{
		return pheap->pdata[0];
	}
	else
	{
		printf("HeapTop::binary tree heap is empty\n");
		return 0;
	}
}

//return binary tree heap data empty
//if heap equal to empty; return true
//else return false
bool HeapEmpty(PBTHeap pheap)
{
	assert(pheap);
	return !pheap->size;
}

//print binary tree heap
void PrintHeap(PBTHeap pheap)
{
	assert(pheap);
	for (int i = 0;i < pheap->size;i++)
	{
		printf("%d ", pheap->pdata[i]);
	}
	printf("\n");
}

//array adjust up to heap
void ArrayToMaxHeap(int* arr, int len)
{
	assert(arr);
	for (int i = 0;i < len;i++)
	{
		MaxAdjustUp(arr, i);
	}
}

//array adjust up to heap
void ArrayToMinHeap(int* arr, int len)
{
	assert(arr);
	for (int i = 0;i < len;i++)
	{
		MinAdjustUp(arr, i);
	}
}

//print array
void PrintArray(int* arr, int len)
{
	assert(arr);
	for (int i = 0;i < len;i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");
}

//heap shot adjust MAX down -> ascending order
void HeapShotUp(int* arr, int len)
{
	assert(arr);
	//array -> MAX heap
	for (int i = 0;i < len;i++)
	{
		MaxAdjustUp(arr, i);
	}
	//array shot
	int templen = len;
	do
	{
		//swap array head member and tail member 
		int temp = arr[0];
		arr[0] = arr[templen - 1];
		arr[templen - 1] = temp;
		templen--;
		//adjust down array head member
		MaxAdjustDown(arr, 0, templen);
	} while (templen > 0);
}

//heap shot adjust MIN down -> descending order
void HeapShotDown(int* arr, int len)
{
	assert(arr);
	//array -> MIN heap
	for (int i = 0;i < len;i++)
	{
		MinAdjustUp(arr, i);
	}
	//array shot
	int templen = len;
	do
	{
		//swap array head member and tail member 
		int temp = arr[0];
		arr[0] = arr[templen - 1];
		arr[templen - 1] = temp;
		templen--;
		//adjust down array head member
		MinAdjustDown(arr, 0, templen);
	} while (templen > 0);
}
